Root-finding algorithms

Bracketing Methods

In these methods, a smaller interval that contains a root is identified iteratively. As these methods do not require any derivatives in general, they are also known as no derivative methods. Some of examples for these methods are:

Bisection method

This method is used for estimatiion of the solution of the equation $f(x) = 0$ for the real variable $x$. Here, $f$ is required to be a continuous function defined on a closed interval $[a, b]$ and $f(a)$ and $f(b)$ have opposite signs. In this case, by the intermediate value theorem, $f$ must have at least one root in the interval $(a, b)$ (for further details see [1-2]).

Iteration tasks

  1. Calculate the midpoint of the interval, $c = \frac{(a + b)}{2}$ and its function value $f(c)$.
  2. If $|f(c)|$ is sufficiently small enough (less than a required tolerance $\epsilon$), return c and stop iterating.
  3. Otherwise, examine the sign of f(c) and replace either $(a,~f(a))$ or $(b,~f(b))$ with $(c,~f(c))$ so that there is a zero crossing within the new interval.

Example: Finding the root of a polynomial.

Suppose that the bisection method is used to find a root of the polynomial $$f(x)=x^{3}-x-2,$$ First, two numbers $a$ and $b$ have to be found such that $f(a)$ and $f(b)$ have opposite signs. Given

For the above function,

Now since $f(a)<0$ and $f(b)>0$, we can implement the method. Let $N_{max}=20$ and the tolerance be $10^{-4}$

Note that the difference between $x_n$ and a solution $x$ is bounded by

$$|c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.$$

Therefore, The number $N_{max}$ of iterations needed to achieve a required tolerance $\epsilon$ is bounded by

$$N_{max}\leq \left\lceil \log _{2}\left({\frac {|b-a|}{\epsilon }}\right)\right\rceil ,$$

In our example, we need at least iterations.

Thus, we can modify our algorithm and remove Nmax from it.

Testing the above example,

Regula falsi

This method is a classic method that estimates a solution using the x-intercept of the line segment joining the endpoints of the function on the current interval. In this method, the root of the equation $f(x) = 0$ for the real variable $x$ is estimated when $f$ is a continuous function defined on a closed interval $[a, b]$ and where $f(a)$ and $f(b)$ have opposite signs. Moreover, $c_n$ is identified:

$$c_{n}={\frac {a_{n}f(b_{n})-b_{n}f(a_{n})}{f(b_{n})-f(a_{n})}}.$$

Thus, for the above example, we have,

There have been also some improved versions of this method. For example, in the Illinois algorithm, $c_n$ is identifed as follows.

$$c_{n}=\dfrac {{\frac {1}{2}}f(b_{n})a_{n}-f(a_{n})b_{n}}{{\frac {1}{2}}f(b_{n})-f(a_{n})}$$

ITP Method

Interpolate Truncate and Project (ITP) method is an improved bisection method that can achive a superlinear convergence of the secant method. In worst-case, it matches the performance of the bisection method.

Furthermore, for the above example, we have,

References

  1. Burden, Richard L., and J. Douglas Faires. "Numerical analysis 8th ed." Thomson Brooks/Cole (2005).
  2. Bisection method Wikipedia page
  3. Regula falsi Wikipedia page
  4. Argyros, I. K., M. A. Hernández-Verón, and M. J. Rubio. "On the Convergence of Secant-Like Methods." Current Trends in Mathematical Analysis and Its Interdisciplinary Applications. Birkhäuser, Cham, 2019. 141-183.
  5. ITP Method